package cn.fansunion.leecode.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 找不同
 * 给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。
https://leetcode-cn.com/problems/find-the-difference/
 * @author wen.lei@brgroup.com
 *
 * 2022-2-16
 */
public class FindTheDifference {
    
    /*示例 1：
    输入：s = "abcd", t = "abcde"
    输出："e"
    解释：'e' 是那个被添加的字母。
    示例 2：
    
    输入：s = "", t = "y"
    输出："y"*/
    
    /**
     * t中的某个字符，在t中出现的次数>在s中出现的次数；3次for循环
     * @param s
     * @param t
     * @return
     */
    public char findTheDifferenceMap(String s, String t) {
        Map<Character, Integer> sCharCountMap = charCountMap(s);
        Map<Character, Integer> tCharCountMap = charCountMap(t);
        for (Character charOfT : t.toCharArray()) {
            final Integer tCharCount = tCharCountMap.get(charOfT);
            final Integer sCharCount = sCharCountMap.get(charOfT);
            //s中可能不存在t
            if(sCharCount==null || tCharCount>sCharCount) {
                return charOfT;
            }
        }
        //没找到，不应该出现
        return '0';
    }
    
    /**
     * 遍历数组，每个字符和对应的次数map
     * @param arr
     * @return
     */
    private Map<Character, Integer> charCountMap(String s) {
        Map<Character, Integer> numCountMap = new HashMap<>();
        for (Character num : s.toCharArray()) {
            Integer count=numCountMap.get(num);
            if(count==null) {
                count=1;
            }else{
                count++;
            }
            numCountMap.put(num, count);
        }
        return numCountMap;
    }
    
    /**
     * 题目和示例描述有歧义，比如：是否存在"abcd"添加了1个a的情况"abcda"，更特殊的"abcda"->"abcdaa"
     * @param s
     * @param t
     * @return
     */
    public char findTheDifferenceBadQuestion(String s, String t) {
        char[] sCharArray=s.toCharArray();
        List<Character> sCharList = new ArrayList<>();
        for (char c : sCharArray) {
            sCharList.add(c);
        }
        for (Character tChar : t.toCharArray()) {
            if(!sCharList.contains(tChar)) {
                return tChar;
            }
        }
        //没找到，一般不会出现；直接习惯返回数字0，没有语法报错，尴尬
        return '0';
    }
}
